/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/contains-duplicate-ii
   @Language: C++
   @Datetime: 20-01-09 10:58
   */

// Time O(n), Space O(k)
class Solution {
public:
	bool containsNearbyDuplicate(vector<int>& nums, int k) {
		unordered_set<int> dict;
		for(int i=0; i<nums.size(); dict.insert(nums[i++])){
			if (dict.size()==k+1) dict.erase(nums[i-k-1]);
			if (dict.count(nums[i])) return true;
		}
		return false;
	}
};
